package jianzhioffer;

/**
 * Author: Zhang Dongwei
 * Date: 2023/3/23 10:12
 * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 */
public class offer_49_丑数 {

    public static void main(String[] args) {
        System.out.println(nthUglyNumber(10));
    }

//    看的解析题解
    public static int nthUglyNumber(int n) {
        int[] dp = new int[n]; // 使用dp数组来存储丑数序列
        dp[0] = 1;
        int a = 0, b = 0, c = 0;
        for (int i=1; i<n; i++){
            int n2 = dp[a]*2, n3 = dp[b]*3, n5 = dp[c]*5;
            dp[i] = Math.min(Math.min(n2, n3), n5);
            if (dp[i] == n2) a++;
            if (dp[i] == n3) b++;
            if (dp[i] == n5) c++;
        }
        return dp[n-1];
    }
}
